#include "string_array.h"
#include <bits/stdc++.h>
using namespace std;

void myStr::print()
{
    for (int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

myStr::myStr(const char *a)
{
    for (int i = 0; a[i] != '\0'; i++)
    {
        length++;
    }
    data = new char[length + 1];
    for (int i = 0; i < length; i++)
    {
        data[i] = a[i];
    }
    data[length] = '\0';
}

myStr::~myStr(){};
bool replaceStr(myStr&S, const int&start, const myStr&T, const myStr&V)
{
    
    int sl=0,vl=0,tl=0;
    while(S.data[sl]!='\0')
    {
        sl++;
    }
    while(T.data[tl]!='\0')
    {
        tl++;
    }
    while(V.data[vl]!='\0')
    {
        vl++;
    }
    if(start-1>=sl||start-1<0||sl<=0) return false;
    int i=start-1;
    int flag=0;
    while(i<=sl-tl)
    {
        flag=0;
        for(int j=0;j<tl;j++)
        {
            if(S.data[i+j]!=T.data[j])
            {
                flag=1;
                break;
            }
        }
        if(flag==0) break;
        i++;
    }
    if(tl==0)
    {
        flag=0;
        i=start-1;
    }
    if(flag==1)
    {
        return false;
    }
    if(vl>tl)
    {
        for(int k=sl;k>=i;k--)
        {
            S.data[k+vl-tl]=S.data[k];
        }
    }
    if(vl<tl)
    {
        for(int k=i+tl;k<sl;k++)
        {
            S.data[k-tl+vl]=S.data[k];
        }
    }
    for(int k=0;k<vl;k++)
    {
        S.data[k+i]=V.data[k];
    }
    S.length=S.length-tl+vl;
    return true;
}
void myStr::kmp_next()
{
    next = new int[length + 1];
    int i = 0;
    next[0] = -1;
    int j = -1;
    while (i < length - 1)
    {
        if (j == -1 || data[i] == data[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
   for (int i = 0; i < length; i++)
       next[i]++;
    return;
};
void myStr::kmp_nextVal()
{
    nextVal = new int[length + 1];
    int i = 0;
    nextVal[0] = -1;
    int j = -1;
    while (i < length - 1)
    {
        if (j == -1 || data[i] == data[j])
        {
            i++;
            j++;
            if (data[i] != data[j])
                nextVal[i] = j;
            else
                nextVal[i] = nextVal[j];
        }
        else
            j = nextVal[j];
    }
    for (int i = 0; i < length; i++)
        nextVal[i]++;

    return;
};

int simpleMatch(const myStr &S, const myStr &T)
{

    int i = 1;
    int j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (S.data[i - 1] == T.data[j - 1])
        {
            ++i;
            ++j;
        }
        else
        {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > T.length)
    {
        return i - T.length;
    }
    else
        return -1;
};

int kmpMatch(const myStr &S, const myStr &T)
{
    int i = 0, j = 0;
    while (i < S.length && j < T.length)
    {
        if (j == -1 || S.data[i] == T.data[j])
        {
            i++;
            j++;
        }
        else
            j = T.next[j];
    }
    if (j >= T.length)
        return i+1 - T.length;
    return -1;
};

void myStr::printNext()
{
    for (int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal()
{
    for (int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

void myMatrix::printMatrix()
{
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for (int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}

bool my_sort(matrixNode A, matrixNode B)
{
    if (A.row < B.row)
    {
        return true;
    }
    else if (A.row > B.row)
    {
        return false;
    }
    else
    {
        if (A.col < B.col)
        {
            return true;
        }
        else if (A.col >= B.col)
        {
            return false;
        }
    }
    return false;
}
myMatrix::myMatrix(const int &rNum, const int &cNum, const int &nNum, const int *data)
{
    rowNum = rNum;
    colNum = cNum;
    nodeNum = nNum;
    nodeList = (matrixNode *)malloc(nNum * sizeof(matrixNode));
    vector<matrixNode> sorted;
    for (int i = 0; i < nNum; i++)
    {
        sorted.push_back({data[3 * i], data[3 * i + 1], data[3 * i + 2]});
    }
    sort(sorted.begin(), sorted.end(), my_sort);
    for (int i = 0; i < sorted.size(); i++)
    {
        nodeList[i].row = sorted[i].row;
        nodeList[i].col = sorted[i].col;
        nodeList[i].value = sorted[i].value;
    }
    return;
};

// 销毁稀疏矩阵，~ myMatrix()
myMatrix::~myMatrix()
{
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
    free(nodeList);
    nodeList = NULL;
    return;
};

myMatrix::myMatrix()
{
    nodeList = NULL;
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
    return;
};

myMatrix::myMatrix(const myMatrix &input)
{
    rowNum = input.rowNum;
    colNum = input.colNum;
    nodeNum = input.nodeNum;
    nodeList = (matrixNode *)malloc(nodeNum * sizeof(matrixNode));
    for (int i = 0; i < nodeNum; i++)
    {
        nodeList[i].row = input.nodeList[i].row;
        nodeList[i].col = input.nodeList[i].col;
        nodeList[i].value = input.nodeList[i].value;
    }
    return;
}

void myMatrix::copy(myMatrix &input)
{
    rowNum = input.rowNum;
    colNum = input.colNum;
    nodeNum = input.nodeNum;
    nodeList = (matrixNode *)malloc(nodeNum * sizeof(matrixNode));
    for (int i = 0; i < nodeNum; i++)
    {
        nodeList[i].row = input.nodeList[i].row;
        nodeList[i].col = input.nodeList[i].col;
        nodeList[i].value = input.nodeList[i].value;
    }
    return;
};
void myMatrix::FastTransposeSMatrix(myMatrix &T)
{
    // myMatrix M;
    T.rowNum = colNum;
    T.colNum = rowNum;
    T.nodeNum = nodeNum;
    T.nodeList = (matrixNode *)malloc(nodeNum * sizeof(matrixNode));
    if (nodeNum <= 0)
        return;
    int num[100001], cpot[100001];
    memset(num, 0, sizeof(num));
    memset(cpot, 0, sizeof(cpot));
    for (int i = 0; i < nodeNum; i++)
        num[nodeList[i].col]++;
    cpot[0] = 0;
    for (int i = 1; i < colNum; i++)
        cpot[i] = cpot[i - 1] + num[i - 1];
    int p = 0, q = 0;
    //	for (int i = 0;i < 5; i++) cout<<num[i]<<' '<<cpot[i]<<endl;
    for (int i = 0; i < nodeNum; i++)
    {
        p = nodeList[i].col;
        q = cpot[p];
        T.nodeList[q].row = nodeList[i].col;
        T.nodeList[q].col = nodeList[i].row;
        T.nodeList[q].value = nodeList[i].value;
        cpot[p]++;
    }
}
int main()
{
    myStr S("hello TJU!");
myStr T("TJU");
myStr T1("NKU");
myStr T2("future");

int isFind;
isFind=replaceStr(S,8,T1,T2);
cout<<isFind<<endl;//0
isFind=replaceStr(S,1,T, T2);
cout<<isFind<<endl;//1
S.print();//hello future!
isFind=replaceStr(S,1,T1, T2);
cout<<isFind<<endl;//0

myStr matchS("acabaabaabcacaabc");
myStr matchT("aabaab");

isFind=simpleMatch(matchS,matchT);
cout<<isFind<<endl;//7

matchS.kmp_next();
matchS.kmp_nextVal();
matchS.printNext();//012123456789
matchS.printNextVal();//002002002009

matchT.kmp_next();
matchT.kmp_nextVal();
matchT.printNext();//012123
matchT.printNextVal();//002003

isFind=kmpMatch(matchS,matchT);
cout<<isFind<<endl;//7

}